Low-Density Parity Check (LDPC) code can achieve performance close to Shannon bound. A m×n parity-check matrix H of a LDPC code is often represented by a bipartite graph, called Tanner graph, which is composed of n bit nodes bj, j=1 to n, and in check nodes ci, i=1 to m. Those bit nodes and check nodes are connected by edges defined by nonzero entries of the check matrix. The decoding performance of LDPC codes is very close to the Shannon limit, when it is operated with iterative message-passing (MP) (or belief propagation, BP) decoding algorithm and sufficiently long code lengths. The sum-product algorithm (SPA), a realization of the MP algorithm, has the best decoding performance among the existing MP-based algorithms.
One of the differences between conventional Error-Correction Codes (ECC) and LDPC codes is that the error-correction ability of LDPC codes is not proven. Thus, a phenomenon called “error floor” will be observed, which means the decoding performance in Bit-Error Ratio (BER) curve will not fall as quickly while the Signal-to-Noise Ratio (SNR) reaches a certain value. To solve this problem, one can concatenate a conventional ECC, e.g. Bose-Chaudhuri-Hocquenghem (BCH) code, after LDPC code but with lower code rate. This method is called serial concatenated coding.
Serial concatenated coding is a technique to combine several error correcting codes into a single one. In general, such a concatenated code can increase the error correcting capability dramatically. Conventionally, a serial concatenated coding employs one conventional ECC code as an outer encoding method and LDPC code as an inner encoding method to obtain a codeword encoded by the two methods sequentially. This coding scheme has several advantages from its powerful correcting capability. For example, due to the systematic characteristics, decoding complexity is often not large. Furthermore, the data read operation can be directly performed by the outer BCH code decoder if the quality of read channel is good. Only when the outer code decoding fails, the inner LDPC code decoder is activated to produce more reliable estimates of the original data.
The encoding and decoding flow chart of serial concatenated coding is shown in FIG. 1. A message is encoded by BCH code first, and then a LDPC code follows. Conversely, the encoded data will be passed to LDPC and then BCH decoders for decoding.
Please see FIG. 2. FIG. 2 shows a decoding procedure of the LDPC and BCH concatenated coding. This figure shows the conventional decoding process (enclosed by dashed-line) of a LDPC code and the additional BCH decoding process. Conventional LDPC decoding processes involve back-and-forth message update iterations between check nodes and bit nodes. The decoded bits are output when the decoded information bits satisfy the zero syndrome vector constraint, or when the iteration number exceeds a maximum number. x denotes the decoded codeword in row vector form in FIG. 2. The iterative decoding of LDPC code will be finished until the maximal iteration count is reached or syndrome test is passed. After that, BCH decoding procedure can be started. As one can see, the executing time of the decoding procedure of LDPC and BCH concatenated coding will be larger than only LDPC decoding is processed so as to reduce the decoding throughput. Therefore, a suitable method to shorten the executing time for decoding serial concatenated coding is necessary.